/*
Source : https://leetcode.com/problems/largest-number/
Author : nflush@outlook.com
Date   : 2016-07-12
*/

/*
179. Largest Number

    Total Accepted: 49674
    Total Submissions: 251310
    Difficulty: Medium

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
Have you met this question in a real interview?
*/

class Solution {
private:
    static bool compare(const int a, const int b)
    {
        
        int ia = a;
        int ib = b;
        if (ia == ib) return false;
        if (ia < ib) return !compare(b, a);
        if (ib == 0) return true;
        int lenB = 1;
        while(ib >= 10){
            lenB *= 10;
            ib/=10;
        }
        ia/=lenB;
        int lenA = lenB;
        while (ia >= 10){
            ia/=10;
            lenA *= 10;
        }

        if (lenA == lenB) return a > b;
        int lenC = (lenA /lenB);
        lenB*=10;
        if (a/lenC > b){
            return true;
        } else if (a/lenC < b){
            return false;
        } else {
            if ((a % lenC) < (a / lenB)){
                return false;
            } else if ((a % lenC) > (a / lenB)){
                return true;
            } else {
                if (a % lenB < b){
                    return true;
                } else{
                    return false;
                }
            }
        }
    }
public:
    string largestNumber(vector<int>& nums) {
        std::sort(nums.begin(), nums.end(), compare);
        string ret;
        if (!nums.size() || nums[0] == 0)return string("0");
        for (int i = 0; i < nums.size(); i++){
            ret += std::to_string(nums[i]);
        }
        return ret;
    }
};
